1. Technical Field
The present invention relates generally to a task scheduling method for a priority-based real-time operating system in a multicore environment and, more particularly, to a method that efficiently schedules tasks in a priority-based Real-Time Operating System (RTOS) installed in a multicore system.
2. Description of the Related Art
Recently, there has been an increase in the number of cases where a multi-core structure is adopted to improve performance relative to power consumption, even in the embedded industry. The use of a multicore structure in an embedded system not only reduces the size of a chip, but also decreases weight and power consumption relative to performance, and thus greatly improves the performance of applications.
However, the use of a multicore structure does not always mean that performance is improved. In some cases, due to low parallelism of an application program, performance may be deteriorated compared to the use of a single core. In order to desirably use a multicore structure, a developer must consider the structure of an application, the partitioning of tasks, the scheduling of tasks, etc. Among these considerations, a task scheduling method is the means contributing most effectively to the improvement of performance.
Conventional real-time multicore task scheduling schemes include a global scheme and a partitioned scheme. As shown in FIG. 1A, the global scheme is configured such that only a single scheduler is present and controls scheduling events of all core processors. In contrast, as shown in FIG. 1B, the partitioned scheme is configured to determine in advance which cores are to be used to execute tasks, partition the tasks, and execute the tasks in the local schedulers of the respective cores.
However, in the Real-Time Operating System (RTOS), there are many cases where tasks are dynamically executed, and thus the above-described conventional real-time multicore task scheduling schemes (global scheme and partitioned scheme) deteriorate efficiency.
Accordingly, for efficiency, a decentralized scheme shown in FIG. 2A or a fully decentralized scheme shown in FIG. 2B is more suitable. This scheme is similar in shape to the partitioned scheme, but has one more scheduling queue. The decentralized or fully decentralized scheme has a hierarchical structure of L1 and L2 levels, wherein L1 functions to distribute tasks and L2 is a single core dedicated local scheduler present in each core.
The global scheme is advantageous in that it is simple and intuitive, but is disadvantageous in that all scheduling events are concentrated on a single scheduler, so that as the number of cores increases, the scheduling overhead increases. Therefore, in the global scheme, once a task is assigned to a core, preemption is made impossible in some cases. This deteriorates real-time properties, thus resulting in problems.
The decentralized scheme has a structure that is extensible even if the number of cores increases, and allows the scheduling overhead to be distributed. However, in this case, when it is considered that most commercial RTOSs use fixed priority policies, there occurs a problem (priority inversion) in which the priority of tasks may be inverted when tasks are assigned to cores. The problem of priority inversion means that a task having lower priority is executed even if a task having higher priority is present in another core. Of course, in a multicore system, there are many cases where, even if some tasks are accidentally executed with the priorities thereof inverted, the performance thereof only slightly decreases, and a serious problem does not occur. However, the frequent occurrence of priority inversion is not so preferable.
As related preceding technology, Korean Patent Application Publication No. 10-2007-0037427 (entitled “Scheduling in a multicore structure”) discloses technology for solving problems that may occur in scheduling used to assign threads in multicore structures.
As another related preceding technology, Korean Patent Application Publication No. 10-2013-0059300 (entitled “Scheduling for supporting real-time properties and Quality of Service (QoS) in a Multicore system”) discloses technology for supporting not only QoS requirements, but also real-time properties in a multicore system.
As further related preceding technology, Korean Patent Application Publication No. 10-2013-0074401 (entitled “Multicore-based computing apparatus having a hierarchical scheduler, and a hierarchical scheduling method therefor”) discloses technology for reducing an unnecessary cache miss and providing a hierarchical scheduling technique optimized for a multicore system.
As yet another related preceding technology, Korean Patent Application Publication No. 10-2013-0088513 (entitled “Task distribution method and apparatus for a multicore system”) discloses technology for incorporating the characteristics of real-time tasks into a system, distributing real-time tasks and non-real-time tasks to the cores of the system, and dynamically solving an imbalance occurring during the execution of tasks.